#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int cherryPickup(vector<vector<int>> &grid)
    {
        int n = grid.size();
        vector<vector<vector<int>>> dp(100, vector<vector<int>>(52, vector<int>(52, INT_MIN)));
        dp[0][1][1] = grid[0][0];
        for (int t = 1; t < 2 * n - 1; ++t)
        {
            for (int a = max(0, t - n + 1); a <= min(t, n - 1); ++a)
            {
                if (grid[a][t - a] < 0)
                    continue;
                for (int b = a; b <= min(t, n - 1); ++b)
                {
                    if (grid[b][t - b] < 0)
                        continue;
                    dp[t][a + 1][b + 1] = max(
                                              max(dp[t - 1][a + 1][b + 1], dp[t - 1][a + 1][b]),
                                              max(dp[t - 1][a][b + 1], dp[t - 1][a][b])) +
                                          grid[a][t - a] + (a == b ? 0 : grid[b][t - b]);
                }
            }
        }
        return max(0, dp[2 * n - 2][n][n]);
    }
};

int main()
{

    // system("pause");
    return 0;
}
